package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

/**
 * @ClassName Medium_55_CanJump
 * @Description Medium_55_CanJump
 * @Author wanghaiwei
 * @Date 2023/3/1 16:57
 */
public class Medium_55_CanJump {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        if (nums.length == 1) {
            return true;
        }
        if (nums[0] == 0) {
            return false;
        }
        //dp中保存了[0-i]能够跳的最远位置
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        //注意i从1到n-1
        for (int i = 1; i < nums.length - 1; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + i);
            if (dp[i] == i) {
                //如果只能原地踏步，就意味着没法往后走了
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Medium_55_CanJump solution = new Medium_55_CanJump();
        boolean result = solution.canJump(new int[]{2, 3, 1, 1, 4});
        Assert.isTrue(result, "[2,3,1,1,4]计算错误，预期true,实际false");
        result = solution.canJump(new int[]{3, 2, 1, 0, 4});
        Assert.isTrue(!result, "[3,2,1,0,4]计算错误，预期false,实际true");
    }
}
